package com.example.demo.leetcode;

/**
 * https://leetcode.cn/problems/container-with-most-water/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * @author WangYX
 * @version 1.0.0
 * @date 2024/02/28 9:46
 */
public class _11_盛最多水的容器 {

    public static void main(String[] args) {
        int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        int i = maxArea(height);
        System.out.println(i);

    }

    /**
     * 双重for循环，超时
     *
     * @param height
     * @return
     */
    public static int maxArea(int[] height) {
        int max = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = i + 1; j < height.length; j++) {
                int width = j - i;
                int high = Math.min(height[i], height[j]);
                max = Math.max(max, width * high);
            }
        }
        return max;
    }

    /**
     * 双指针+ 贪心
     *
     * @author WangYX
     * @date 2024/02/28 10:08
     * @version 1.0.0
     */
    public static int maxArea1(int[] height) {
        int max = 0;
        int i = 0, j = height.length - 1;

        while (i < j) {
            max = Math.max(max, Math.min(height[j], height[i]) * (j - i));
            if (height[j] > height[i]) {
                i++;
            } else {
                j--;
            }
        }

        return max;
    }
}
